package com.example.system.class05;

import java.util.Arrays;

/**
 * @Date 2022/7/23
 * @Author Jonathan
 * <p/>
 * 在一个数组中，
 * 对于每个数num，求有多少个后面的数*2依然小于num，求总个数
 * 比如：[3,1,7,0,2]
 * 3的后面有：1，0
 * 1的后面有：0
 * 7的后面有：0，2
 * 0的后面没有
 * 2的后面没有
 * 所以总共有5个
 */
public class Code04_BiggerThanRightTwice {
    // 老规矩 先写归并排序
    public static void main(String[] args) {
        int[] arr = new int[]{3, 1, 7, 0, 2};
        //int[] arr = new int[]{8, 9, 1, 2};
        final int process = process(arr, 0, arr.length - 1);
        System.out.println(process);
        System.out.println(Arrays.toString(arr));
    }


    public static int process(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int middle = left + ((right - left) >> 1);
        int l = process(arr, left, middle);
        int r = process(arr, middle + 1, right);
        final int merge = merge(arr, left, middle, right);
        return l + r + merge;

    }

    public static int merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int index = 0;
        int l = left;
        int r = mid + 1;
        int ans = 0;
        while (l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                help[index++] = arr[l++];
            } else {
                // arr[l] > arr[r]
                // arr[l...mid] 有序的
                int mostLeft = l;
                while (mostLeft <= mid) {
                    // 要遍历完 满足的条件的计数加一
                    if (arr[mostLeft] > arr[r] * 2) {
                        System.out.println(arr[mostLeft] + "__" + arr[r]);
                        ans++;
                    }
                    mostLeft++;
                }
                help[index++] = arr[r++];
            }
        }
        while (l <= mid) {
            help[index++] = arr[l++];
        }

        while (r <= right) {
            help[index++] = arr[r++];
        }
        // copy
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return ans;
    }

}
